class Solution {
public:
    class greater{
    public:
        bool operator()(const pair<int,int>& a,const pair<int,int>& b){
            return a.second > b.second;
        }
    };
    
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        vector<vector<pair<int,int> > > G(n);
        for(auto& vc : edges){
            G[vc[0]].push_back({vc[1],vc[2]});
            G[vc[1]].push_back({vc[0],vc[2]});
        }
    
        
        vector<int> dist(n,INT_MAX);
        map<pair<int,int>,int> used;
        dist[0] = 0;
        
        priority_queue<pair<int,int>,vector<pair<int,int> > ,greater> que;
        que.push({0,0});
        
        int ret = 0;
    
        while(!que.empty()){
            auto kv = que.top();
            que.pop();
            int u = kv.first;
            int cnt = kv.second;
            if(cnt > dist[u]){
                continue;
            }
            
            ++ret;
            
            for(auto& [v,w] : G[u]){
                used[{u,v}] = min(w,maxMoves-dist[u]);
                
                if(dist[u]+w+1 < min(dist[v],maxMoves+1)){
                    dist[v] = dist[u]+w+1;
                    que.push({v,dist[v]});
                }
            }
        }
        
        for (vector<int> edge: edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            ret += min(w, used[{u, v}] + used[{v, u}]);
        }
        
        return ret;
        
    }
};
